package com.ztom.top100;

/**
 * 完全平方数
 * <p>
 * https://leetcode-cn.com/problems/perfect-squares/
 *
 * @author ZhangTao
 */
public class Code72NumSquares {

    public int numSquares2(int n) {
        return process(n);
    }

    private int process(int n) {
        if (n == 0) {
            // n = 0 时无法表示
            return 0;
        }
        int min = Integer.MAX_VALUE;
        // 枚举每个数的平方, 收集所需要的最小个数
        for (int i = 1; i * i <= n; i++) {
            min = Math.min(min, process(n - i * i));
        }
        return min + 1;
    }

    public int numSquares1(int n) {
        int[] dp = new int[n + 1];
//        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }

    /**
     * 数学公式法
     * https://baike.baidu.com/item/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        if (isPerfectSquare(n)) {
            return 1;
        }
        if (is4(n)) {
            return 4;
        }
        for (int i = 1; i * i <= n; i++) {
            if (isPerfectSquare(n - i * i)) {
                return 2;
            }
        }
        return 3;
    }

    private boolean isPerfectSquare(int n) {
        int x = (int) Math.sqrt(n);
        return x * x == n;
    }

    private boolean is4(int n) {
        while (n % 4 == 0) {
            n /= 4;
        }
        return n % 8 == 7;
    }
}
